МІНІСТЕРСТВО ОСВІТИ І НАУКИ УКРАЇНИ
НАЦІОНАЛЬНИЙ УНІВЕРСИТЕТ “ЛЬВІВСЬКА ПОЛІТЕХНІКА”
СТИСНЕННЯ ІНФОРМАЦІЇ МЕТОДОМ LZW
МЕТОДИЧНІ ВКАЗІВКИ
до лабораторної роботи з курсу
“Проблемно-орієнтовані методи та засоби комп’ютерних
інформаційних технологій”
для студентів базового напрямку
6.08.04 “Комп’ютерні науки”
Затверджено
на засіданні кафедри
“Системи автоматизації проектування”
Протокол № 9 від 07.02.2002 р.
Львів – 2002
Стиснення інформації методом LZW: Методичні вказівки до лабораторної роботи з курсу “Методи та засоби комп’ютерних інформаційних технологій” для студентів базового напрямку 6.08.04 “Комп’ютерні науки”.
/ Укл.: В.В. Мазур. – Львів: Видавництво Національного університету “Львівська політехніка”, 2002. - 7 с.
Укладач Мазур В.В., канд, техн, наук, доц.
Відповідальний за випуск Ткаченко С.П., канд, техн. наук, доц.
Рецензенти Каркульовський В.І., канд. техн.наук.,доц.
Кравець П.О., канд.техн.наук, доц.
МЕТА РОБОТИ
Мета роботи - вивчення методу Лемпеля-Зіва-Велча (LZW) для стиснення даних та його програмної реалiзацiї для практичного використання.
КОРОТКІ ТЕОРЕТИЧНІ ВІДОМОСТІ
2.1. Стиснення даних.
З метою компактного представлення інформації в ПЕОМ для її збереження (архівації) чи передачі по каналу зв’язку широко використовується стиснення даних. Методи стиснення даних поділяються на дві групи: стиснення без втрат і стиснення з втратами. Крім того, методи групуються в залежності від характеру інформації, що стискається: стиснення символьної інформації (документів), стиснення нерухомих графічних зображень (JPEG) і стиснення рухомих графічних зображень (MPEG). Основним параметром, що характеризує рівень стиснення інформації є коефіцієнт стиснення, який визначається відношенням обсягу нестиснених даних до обсягу стиснених (наприклад 5:1).
2.2. Метод LZW.
Відомі методи оптимального кодування різнозначними кодами (кодами різної довжини), які базуються на врахуванні різної частоти символів в тексті. Найбільш відомі з них: метод Шеннона-Фано та метод Хаффмана. Ці методи забезпечують достатньо ефективне стиснення без втрат. Для підвищення рівня стиснення даних доцільно перейти від оптимального кодування окремих символів до кодування буквосполучень. Саме таке кодування забезпечує метод LZW.
Метод базується на побудові таблиці фраз (словника), яка відображає стрічки символів повідомлення, що стискається, в коди фіксованої довжини (12 біт). Таблиця має властивість попередництва, тобто для кожної фрази словника, яка складається з деякої фрази w і символа K, фраза w теж міститься в словнику і представляється відповідним номером n.
Програмна реалізація методу здійснюється за наступним алгоритмом (ілюструється на прикладі кодування фрази МАМАМАЛАЛАМУ з представленням словника у вигляді таблиці:
У словник заносяться односимвольні фрази w, що відповідають символам вхідного алфавіту (ініціація словника).
Біжучий вказівник встановлюється на перший символ тексту (фраза М).
Здійснюється пошук фрази М у словнику (фраза є за номером 1).
Фраза М доповнюється наступним символом А і здійснюється пошук розширеної фрази МА у словнику (фраза відсутня).
Знайдена раніше частина розширеної фрази МА (фраза М) кодується її номером 1, а нова фраза МА заноситься у словник під номером 5 і представляється (у формі nK) кодом 1А.
Після цього, вказівник встановлюється на останній символ А розширеної фрази МА, який розглядається і кодується як нова фраза, аналогічно як у п. 3.
Фраза А є у словнику під номером 2.
Фраза А доповнюється наступним символом М і здійснюється пошук розширеної фрази АМ у словнику (фраза відсутня).
Знайдена частина розширеної фрази АМ (фраза а) кодується її номером 2, а нова фраза АМ заноситься в словник під номером 6 і представляється кодом 2М.
Вк...
